﻿// Copyright (c) 2009, Heiko Wundram (modelnine@h8me.eu).
// All rights reserved.
//
// Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following
// conditions are met:
//
// * Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.
// * Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer
//   in the documentation and/or other materials provided with the distribution.
// * Neither the name of Heiko Wundram (h8me.eu) nor the names of its contributors may be used to endorse or promote products
//   derived from this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING,
// BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT
// SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
// DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
// NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

using System;
using System.Collections.Generic;

namespace eu.h8me.Parsing.ParserLib {

    /// <summary>
    /// Helper class representing an LR item as used in the LR item sets describing the finite automaton of the grammar.
    /// </summary>
    internal class LRItem : IComparable<LRItem> {

        // Data.
        private readonly Symbol _Symbol;
        private readonly int _Production;
        private readonly int _RulePosition;
        private int? _Hash;

        /// <summary>
        /// Initialize a new LR item from the specified production, attached to the specified non-terminal and being positioned
        /// at the specified position in the production.
        /// </summary>
        /// <param name="symb">Non-terminal symbol making up this LR item.</param>
        /// <param name="prod">Production index in the non-terminal that describes this LR item.</param>
        /// <param name="pos">Position inside the LR item.</param>
        public LRItem(Symbol symb, int prod, int pos) {
            // Initialize LR item.
            _Symbol = symb;
            _Production = prod;
            _RulePosition = pos;
        }

        /// <summary>
        /// Fetch the symbol associated with this LR item.
        /// </summary>
        public Symbol Symbol {
            get {
                // Return symbol.
                return _Symbol;
            }
        }

        /// <summary>
        /// Fetch the production index of this LR item.
        /// </summary>
        public int Production {
            get {
                // Return production index.
                return _Production;
            }
        }

        /// <summary>
        /// Fetch the actual production rule describing this LR item.
        /// </summary>
        public Production ProductionRule {
            get {
                // Return production.
                return _Symbol[_Production];
            }
        }

        /// <summary>
        /// Fetch the current rule position inside the production.
        /// </summary>
        public int RulePosition {
            get {
                // Return position access.
                return _RulePosition;
            }
        }

        /// <summary>
        /// Check whether the bound production has a symbol that follows the current position inside the rule.
        /// </summary>
        public bool HasNextSymbol {
            get {
                return _Symbol[_Production].Count > _RulePosition;
            }
        }

        /// <summary>
        /// Fetch the next symbol that follows the current position in the production.
        /// </summary>
        public Symbol NextSymbol {
            get {
                return _Symbol[_Production][_RulePosition];
            }
        }

        /// <summary>
        /// Build a hash value that describes this LR item. Equal LR items have equal hash codes.
        /// </summary>
        /// <returns>Hash value containing info on this LR item.</returns>
        public override int GetHashCode() {
            // Calculate hash if not done yet.
            if( !_Hash.HasValue )
                _Hash = _Symbol.GetHashCode() ^ ( ( _Production << 8 ) | ( _Production >> 24 ) ) ^
                    ( ( _RulePosition << 24 ) | ( _RulePosition >> 8 ) );

            // Return hash.
            return _Hash.Value;
        }

        /// <summary>
        /// Compare item against other, returning true iff both are LR items and are equivalent.
        /// </summary>
        /// <param name="obj">Object to compare to.</param>
        /// <returns>Comparison result.</returns>
        public override bool Equals(object obj) {
            // Cast to LRItem and check for equality.
            LRItem other = obj as LRItem;
            return other != null && _Symbol == other._Symbol && _Production == other._Production &&
                _RulePosition == other._RulePosition;
        }

        /// <summary>
        /// Return an integer describing the relative position of this LR item against another. This is used by the item set to
        /// implement faster comparisons of item sets. The ordering is completely defined, but otherwise arbitrary.
        /// </summary>
        /// <param name="other">Other item to compare against.</param>
        /// <returns>-1 when this item is less than other, 1 when this item is greater than other, 0 when equivalent.</returns>
        public int CompareTo(LRItem other) {
            // Compare contained symbols.
            int rv;
            if( ( rv = _Symbol.CompareTo(other._Symbol) ) != 0 )
                // Symbols don't compare equal.
                return rv;
            else if( ( rv = _Production.CompareTo(other._Production) ) != 0 )
                // Productions don't compare equal.
                return rv;

            // Return result of rule position comparison.
            return _RulePosition.CompareTo(other._RulePosition);
        }

    }

    /// <summary>
    /// Helper class storing a set of LR items and the associated lookahead. LR item sets make up the finite automaton
    /// describing a grammar.
    /// </summary>
    internal class LRItemSet : IEnumerable<KeyValuePair<LRItem, SortedDictionary<Symbol, bool>>> {

        // Data.
        private readonly SortedDictionary<LRItem, SortedDictionary<Symbol, bool>> _Items =
            new SortedDictionary<LRItem, SortedDictionary<Symbol, bool>>();
        private readonly HashSet<Symbol> _NextSymbols = new HashSet<Symbol>();
        private bool _Changed;
        private bool _Updated;
        private int? _Hash;

        /// <summary>
        /// Initialize a new, empty LR item set.
        /// </summary>
        public LRItemSet() {
            // No specific construction.
        }

        /// <summary>
        /// Attach the specified LR item with the passed lookahead to the current LR item set.
        /// </summary>
        /// <param name="item">LR item to add.</param>
        /// <param name="la">Lookahead for the item to add.</param>
        public void Add(LRItem item, IEnumerable<Symbol> la) {
            // Check whether item is present already.
            SortedDictionary<Symbol, bool> curla;
            if( !_Items.TryGetValue(item, out curla) ) {
                // No, not present, create it and attach possible next symbol.
                _Items[item] = curla = new SortedDictionary<Symbol, bool>();
                if( item.HasNextSymbol )
                    _NextSymbols.Add(item.NextSymbol);

                // Set up changed state.
                _Changed = _Updated = true;
            }

            // Insert the new lookaheads.
            foreach( Symbol symb in la ) {
                if( !curla.ContainsKey(symb) ) {
                    // Is an update.
                    curla[symb] = true;
                    _Updated = true;
                }
            }
        }

        /// <summary>
        /// Fetch list of symbols following the LR items contained in this item set.
        /// </summary>
        public IEnumerable<Symbol> NextSymbols {
            get {
                // Return calculated set of next symbols.
                return _NextSymbols;
            }
        }

        /// <summary>
        /// Check whether adding the last LR items since calling ResetState() changed this item set, i.e. added a new item to
        /// the set of items. This is used by the closure operation to check whether to restart an iteration. When Changed is
        /// true, this implies that Updated is also true.
        /// </summary>
        public bool Changed {
            get {
                // Return changed state.
                return _Changed;
            }
        }

        /// <summary>
        /// Check whether adding the last LR items since calling ResetState() updated lookahead for an existing LR item. This
        /// is used by the closure operation to check for finish.
        /// </summary>
        public bool Updated {
            get {
                // Return updated state.
                return _Updated;
            }
        }

        /// <summary>
        /// Reset the current LR item state for a new iteration of the closure operation.
        /// </summary>
        public void ResetState() {
            // Set updated and changed to false.
            _Changed = false;
            _Updated = false;
        }

        /// <summary>
        /// Fetch a hash code describing this LR item set. Equivalent LR items have equivalent hash codes.
        /// </summary>
        /// <returns>Has code describing this item set.</returns>
        public override int GetHashCode() {
            // Check for existing hash value.
            if( !_Hash.HasValue ) {
                // Hash all items (in the sort order they are in the dictionaries).
                int hash = 0;
                foreach( KeyValuePair<LRItem, SortedDictionary<Symbol, bool>> item in _Items ) {
                    // Hash LR item and lookahead symbols for this LRItemSet.
                    hash = ( ( hash << 5 ) | ( hash >> 27 ) ) ^ item.Key.GetHashCode();
                    foreach( Symbol la in item.Value.Keys )
                        hash = ( ( hash << 7 ) | ( hash >> 25 ) ) ^ la.GetHashCode();
                }

                // Store hash.
                _Hash = hash;
            }

            // Return hash.
            return _Hash.Value;
        }

        /// <summary>
        /// Compare this item set against another, returning true iff they are equivalent.
        /// </summary>
        /// <param name="obj">Object to compare against.</param>
        /// <returns>Returns true iff the object references an item set and is equal to this item set.</returns>
        public override bool Equals(object obj) {
            // Convert to LRItemSet and check preconditions.
            LRItemSet other = obj as LRItemSet;
            if( other == null || ( _Hash.HasValue && other._Hash.HasValue && _Hash.Value != other._Hash.Value ) ||
                _Items.Count != other._Items.Count )
                return false;

            // Loop over the items, comparing the elements in turn (which must match because they are sorted equally).
            IEnumerator<KeyValuePair<LRItem, SortedDictionary<Symbol, bool>>>[] dicts =
                new IEnumerator<KeyValuePair<LRItem, SortedDictionary<Symbol, bool>>>[] {
                    _Items.GetEnumerator(), other._Items.GetEnumerator()
                };
            while( dicts[0].MoveNext() && dicts[1].MoveNext() ) {
                // If the items don't match (they must, because both dicts are sorted), return immediately.
                if( dicts[0].Current.Key.CompareTo(dicts[1].Current.Key) != 0 ||
                    dicts[0].Current.Value.Count != dicts[1].Current.Value.Count )
                    return false;

                // Compare elements. They are in sorted order, so we can compare them directly. If this finishes, the sets are
                // equal (because they are equally sized).
                IEnumerator<KeyValuePair<Symbol, bool>>[] subdicts = new IEnumerator<KeyValuePair<Symbol, bool>>[] {
                    dicts[0].Current.Value.GetEnumerator(), dicts[1].Current.Value.GetEnumerator()
                };
                while( subdicts[0].MoveNext() && subdicts[1].MoveNext() )
                    // Check subelement.
                    if( subdicts[0].Current.Key != subdicts[1].Current.Key )
                        return false;
            }

            // When we get here, the comparison worked out (because both lists are of equal length).
            return true;
        }

        /// <summary>
        /// Number of LR items stored in this item set.
        /// </summary>
        public int Count {
            get {
                // Return item count.
                return _Items.Count;
            }
        }

        /// <summary>
        /// Return a typed enumerator over the contained LR items and their lookahead.
        /// </summary>
        /// <returns>Enumerator listing the LR items contained in this set and their respective lookahead.</returns>
        public IEnumerator<KeyValuePair<LRItem, SortedDictionary<Symbol, bool>>> GetEnumerator() {
            // Return enumerator on contained items.
            return _Items.GetEnumerator();
        }

        /// <summary>
        /// Return an untyped enumerator over the contained LR items and their lookahead.
        /// </summary>
        /// <returns>Enumerator listing the LR items contained in this set and their respective lookahead.</returns>
        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() {
            // Return untyped enumerator on contained items.
            return _Items.GetEnumerator();
        }

    }

}
